import java.util.Arrays;

// https://leetcode.cn/problems/coin-change/submissions/
// 先物品再背包
class Solution {
    public int numSquares(int n) {
        // dp[i] 和为 i 的完全平方数的最少数量
        int[] dp = new int[n + 1];
        Arrays.fill(dp, 1, dp.length, Integer.MAX_VALUE);
        for (int i = 1; i * i <= n; i++) // 物品
            for (int j = i * i; j <= n; j++) // 背包
                dp[j] = Math.min(dp[j], dp[j - i * i] + 1);
        return dp[n];
    }
}

// 先背包再物品
class Solution1 {
    public int numSquares(int n) {
        int[] dp = new int[n + 1];
        Arrays.fill(dp, 1, dp.length, Integer.MAX_VALUE);
        for (int i = 0; i <= n; i++) // 背包
            for (int j = 1; j * j <= i; j++) // 物品
                dp[i] = Math.min(dp[i], dp[i - j * j] + 1);
        return dp[n];
    }
}